function MyLinkedList() {
    //头节点指针
    this._head = null;
    //尾节点指针
    this._last = null;
    //链表实际长度
    this._size = 0;
}

MyLinkedList.prototype.insert = function(index, data) {
    if (index < 0 || index > this._size) {
        throw new Error("超出链表节点范围！");
    }
    var insertedNode = {
        data: data,
        next: null
    };
    if(this._size == 0){
        //空链表
        this._head = insertedNode;
        this._last = insertedNode;
    } else if(index == 0){
        //插入头部
        insertedNode.next = this._head;
        this._head = insertedNode;
    }else if(this._size == index){
        //插入尾部
        this._last.next = insertedNode;
        this._last = insertedNode;
    }else {
        //插入中间
        var prevNode = this.get(index-1);
        insertedNode.next = prevNode.next;
        prevNode.next = insertedNode;
    }
    this._size++;
}

MyLinkedList.prototype.remove = function(index) {
    if (index < 0 || index >= this._size) {
        throw new Error("超出链表节点范围！");
    }
    var removedNode = null;
    if(index == 0){
        //删除头节点
        removedNode = this._head;
        this._head = this._head.next;
    } else if(index == this._size - 1){
        //删除尾节点
        var prevNode = this.get(index-1);
        removedNode = prevNode.next;
        prevNode.next = null;
        this._last = prevNode;
    } else {
        //删除中间节点
        var prevNode = this.get(index-1);
        var nextNode = prevNode.next.next;
        removedNode = prevNode.next;
        prevNode.next = nextNode;
    }
    this._size--;
    return removedNode;
}

MyLinkedList.prototype.get = function(index) {
    if (index < 0 || index >= this._size) {
        throw new Error("超出链表节点范围！");
    }
    var temp = this._head;
    for(var i=0; i < index; i++){
        temp = temp.next;
    }
    return temp;
}

MyLinkedList.prototype.output = function(){
    var temp = this._head;
    while (temp != null) {
        console.log(temp.data);
        temp = temp.next;
    }
}

var myLinkedList = new MyLinkedList();
myLinkedList.insert(0,3);
myLinkedList.insert(0,4);
myLinkedList.insert(2,9);
myLinkedList.insert(3,5);
myLinkedList.insert(1,6);
myLinkedList.remove(0);
myLinkedList.output();